import java.io.*;
import java.math.BigInteger;


public class FastNumericalCoding {
	public static String code(byte[] x) throws UnsupportedEncodingException {
		int[] tau = Utils.tau(x);
		int[] tauBackup = tau.clone();

        BigInteger F = BigInteger.ZERO;
        BigInteger G = BigInteger.ONE;

		int[] q = new int[Utils.size + 1];
		q[0] = 0;

        BigInteger fact = BigInteger.ONE;

		for (int i = 0; i < x.length; i++) {
			int n = x.length - i;
            BigInteger N = BigInteger.valueOf(n);
			
			for (int j = 1; j <= Utils.size; j++) {
				q[j] = q[j - 1] + tau[j - 1];
			}
			
			int xi = x[i] & 255;

            F = F.multiply(N).add(G.multiply(BigInteger.valueOf(q[xi])));
            G = G.multiply(BigInteger.valueOf(tau[xi]));
            fact = fact.multiply(N);

			tau[xi]--;

            if ((i + 1) % 1000 == 0) {
                System.err.println((i + 1) + " / " + x.length);
            }
		}
        System.err.println("F and G done");

		int z = new Fraction(fact, G).log2up();
        System.err.println("z done");
		String out = new Fraction(F, fact).nBitsAfterComma(z).toString(2);
        System.err.println("out done");
        StringBuilder res = new StringBuilder(Utils.tauIndex(tauBackup) + "|");
        System.err.println("tau index done");
        int newZero = 0;
        while (newZero + out.length() < z) {
			res.append("0");
            ++newZero;
		}
        res.append(out);
		return res.toString();
	}
	
	public static void main (String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("input-big.txt"), "cp1251"));
        StringBuilder data = new StringBuilder();
        String line;
        while ((line = in.readLine()) != null) {
            data.append(line).append("\n");
        }
		String input = data.toString();
		in.close();
		String output = code(input.getBytes("cp1251"));
		System.out.println();
		System.out.println(output);
		System.out.println("Input length: " + input.length() * 8 + " bits");
		System.out.println("Output length: " + (output.length() - 1) + " bits");
		System.out.println("Output-tau: " + (output.indexOf('|')) + " bits");
		System.out.println("Output-data: " + (output.length() - 1 - output.indexOf('|')) + " bits");
	}
}	
